package graph

import (
	"math"

	"gitee.com/yrwy/msgo/pkg/mem/stl/heap"
)

func Dijkstra[T comparable](g Grapher[T], s T) Tree[T] {
	w := make(map[T]int)
	h := heap.NewHeap[T](func(l, r T) bool {
		return w[l] < w[r]
	})
	p := g.NewTree()
	w[s] = 0
	sure := make(map[T]bool)
	u := s
	h.Push(s)
	for h.Len() > 0 {
		u = h.Pop()
		sure[u] = true
		adj := g.Adjacency(u)
		for _, v := range adj {
			if sure[v] {
				continue
			}
			wt := w[u] + g.Weight(u, v)
			if w[v] == math.MaxInt {
				//加入新节点
				p.Set(v, u)
				w[v] = wt
				h.Push(v)
			} else {
				if wt < w[v] {
					//重置为权值更小的路径
					w[v] = wt
					p.Set(v, u)
				}
			}
		}
	}
	return p
}
